﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using KLadderProposal.Interfaces;
using KLadderProposal.Interfaces.BasicStructures;

namespace KLadderProposal.Algorithms
{
    public class MultiLevelAlgorithm : IAlgorithm
    {
        private List<List<GraphNode>> _triangles = new List<List<GraphNode>>();
        private List<List<List<GraphNode>>> _trianglesByClusters = new List<List<List<GraphNode>>>();
        private int _index = 0;
        private List<GraphNode> _removedNodes = new List<GraphNode>();
        private int _level = 0;
        private const int NeighborThreshhold = 2;

        public void Run(IGraph graph)
        {
            while (RunRecursive(graph))
            {
                _level++;
            }
        }

        private bool RunRecursive(IGraph graph)
        {
            bool isCliqueFound = false;
            bool innerIsCliqueFound = false;

            foreach (GraphNode node1 in graph.Nodes.ToArray())
            {
                innerIsCliqueFound = false;

                if (_removedNodes.Contains(node1))
                    continue;

                foreach (GraphNode node2 in graph.Nodes.ToArray())
                {
                    if (node1 == node2)
                        continue;

                    if (node2.Level > _level)
                        continue;

                    if (!node1.Neighbors.ContainsKey(node2.Label))
                        continue;

                    if (_removedNodes.Contains(node2))
                        continue;

                    foreach (GraphNode node3 in graph.Nodes.ToArray())
                    {
                        if (node3 == node1 || node3 == node2)
                            continue;

                        if (node3.Level > _level)
                            continue;

                        if (!node1.Neighbors.ContainsKey(node3.Label) || !node2.Neighbors.ContainsKey(node3.Label))
                            continue;

                        if (_removedNodes.Contains(node3))
                            continue;

                        foreach (GraphNode node4 in graph.Nodes.ToArray())
                        {
                            if (node4 == node1 || node4 == node2 || node4 == node3)
                                continue;

                            if (node4.Level > _level)
                                continue;

                            if (!node1.Neighbors.ContainsKey(node4.Label) || !node2.Neighbors.ContainsKey(node4.Label)
                                || !node3.Neighbors.ContainsKey(node4.Label))
                                continue;

                            if (_removedNodes.Contains(node4))
                                continue;

                            if (IsNClique(new List<GraphNode>{node1, node2, node3, node4}))
                            {
                                isCliqueFound = true;
                                innerIsCliqueFound = true;
                                ReplaceCliqueByNode(graph, node1, node2, node3, node4);
                                break;
                            }
                        }
                        if (innerIsCliqueFound)
                            break;
                    }
                    if (innerIsCliqueFound)
                        break;
                }
            }

            return isCliqueFound;
        }

        private void ReplaceCliqueByNode(IGraph graph, GraphNode node1, GraphNode node2, GraphNode node3, GraphNode node4)
        {
            List<GraphNode> cliquesNeighbors = new List<GraphNode>();

            foreach (GraphNode node4Negbor in node4.Neighbors.Values.Where(node=>node != node1 && node!= node2 && node!=node3))
                cliquesNeighbors.Add(node4Negbor);

            foreach (GraphNode node3Negbor in node3.Neighbors.Values.Where(node => node != node1 && node != node2 && node != node4))
                cliquesNeighbors.Add(node3Negbor);

            foreach (GraphNode node2Negbor in node2.Neighbors.Values.Where(node => node != node1 && node != node4 && node != node3))
                cliquesNeighbors.Add(node2Negbor);

            foreach (GraphNode node1Negbor in node1.Neighbors.Values.Where(node => node != node4 && node != node2 && node != node3))
                cliquesNeighbors.Add(node1Negbor);

            graph.Remove(node1.Label);
            graph.Remove(node2.Label);
            graph.Remove(node3.Label);
            graph.Remove(node4.Label);

            _removedNodes.Add(node1);
            _removedNodes.Add(node2);
            _removedNodes.Add(node3);
            _removedNodes.Add(node4);

            cliquesNeighbors = cliquesNeighbors.Distinct().ToList();
            List<string> sortedNames = new List<string>{node1.Label, node2.Label, node3.Label, node4.Label};
            sortedNames.Sort();
            
            string newNodeName = sortedNames.Aggregate((first,second)=>first + "_" + second);
 
            GraphNode newNode = graph.AddNode(newNodeName);
            newNode.Level = _level + 1;
            if (cliquesNeighbors.Count > 0)
            {
                foreach (GraphNode cliqueNeighbor in cliquesNeighbors)
                    graph.AddUndirectedEdge(newNodeName, cliqueNeighbor.Label);
            }
        }

        private bool IsNClique(List<GraphNode> nodes)
        {
            nodes.Sort((x,y)=> x.Label.CompareTo(y.Label));

            for (int i = 0; i < nodes.Count - 1; i++)
            {
                bool result = false;
                List<bool> found = new List<bool>();
                found.AddRange(Enumerable.Repeat(false, nodes.Count - i - 1));
                int j = 0;

                foreach (GraphNode nodeNeighbor in nodes[i].Neighbors.Values)
                {
                    if (!found[j] && nodes[i+j+1] == nodeNeighbor)
                    {
                        found[j] = true;
                        j++;
                    }

                    if (found.All(foundInner => foundInner))
                    {
                        result = true;
                        break;
                    }
                }

                if (!result)
                    return false;
            }

            return true;
        }
    }

    public class MultiLevelAlgorithm2 : IAlgorithm
    {
        private List<List<GraphNode>> _triangles = new List<List<GraphNode>>();
        private List<List<List<GraphNode>>> _trianglesByClusters = new List<List<List<GraphNode>>>();
        private int _index = 0;
        private List<GraphNode> _removedNodes = new List<GraphNode>();
        private int _level = 0;
        private const int NeighborThreshhold = 2;

        public void Run(IGraph graph)
        {


            while (RunRecursive(graph))
            {
                _level++;
            }
        }

        private bool RunRecursive(IGraph graph)
        {
            bool isCliqueFound = false;
            bool innerIsCliqueFound = false;

            foreach (GraphNode node1 in graph.Nodes.ToArray())
            {
                innerIsCliqueFound = false;

                if (_removedNodes.Contains(node1))
                    continue;

                foreach (GraphNode node2 in graph.Nodes.ToArray())
                {
                    if (node1 == node2)
                        continue;

                    if (node2.Level > _level)
                        continue;

                    if (_removedNodes.Contains(node2))
                        continue;

                    foreach (GraphNode node3 in graph.Nodes.ToArray())
                    {
                        if (node3 == node1 || node3 == node2)
                            continue;

                        if (node3.Level > _level)
                            continue;

                        if (_removedNodes.Contains(node3))
                            continue;

                        foreach (GraphNode node4 in graph.Nodes.ToArray())
                        {
                            if (node4 == node1 || node4 == node2 || node4 == node3)
                                continue;

                            if (node4.Level > _level)
                                continue;

                            if (_removedNodes.Contains(node4))
                                continue;

                            if (IsNClique(new List<GraphNode> { node1, node2, node3, node4 }))
                            {
                                isCliqueFound = true;
                                innerIsCliqueFound = true;
                                ReplaceCliqueByNode(graph, node1, node2, node3, node4);
                                break;
                            }
                        }
                        if (innerIsCliqueFound)
                            break;
                    }
                    if (innerIsCliqueFound)
                        break;
                }
            }

            return isCliqueFound;
        }

        private void ReplaceCliqueByNode(IGraph graph, GraphNode node1, GraphNode node2, GraphNode node3, GraphNode node4)
        {
            List<GraphNode> cliquesNeighbors = new List<GraphNode>();

            foreach (GraphNode node4Negbor in node4.Neighbors.Values.Where(node => node != node1 && node != node2 && node != node3))
                cliquesNeighbors.Add(node4Negbor);

            foreach (GraphNode node3Negbor in node3.Neighbors.Values.Where(node => node != node1 && node != node2 && node != node4))
                cliquesNeighbors.Add(node3Negbor);

            foreach (GraphNode node2Negbor in node2.Neighbors.Values.Where(node => node != node1 && node != node4 && node != node3))
                cliquesNeighbors.Add(node2Negbor);

            foreach (GraphNode node1Negbor in node1.Neighbors.Values.Where(node => node != node4 && node != node2 && node != node3))
                cliquesNeighbors.Add(node1Negbor);

            graph.Remove(node1.Label);
            graph.Remove(node2.Label);
            graph.Remove(node3.Label);
            graph.Remove(node4.Label);

            _removedNodes.Add(node1);
            _removedNodes.Add(node2);
            _removedNodes.Add(node3);
            _removedNodes.Add(node4);

            cliquesNeighbors = cliquesNeighbors.Distinct().ToList();
            List<string> sortedNames = new List<string> { node1.Label, node2.Label, node3.Label, node4.Label };
            sortedNames.Sort();

            string newNodeName = sortedNames.Aggregate((first, second) => first + "_" + second);

            GraphNode newNode = graph.AddNode(newNodeName);
            newNode.Level = _level + 1;
            if (cliquesNeighbors.Count > 0)
            {
                foreach (GraphNode cliqueNeighbor in cliquesNeighbors)
                    graph.AddUndirectedEdge(newNodeName, cliqueNeighbor.Label);
            }
        }

        private bool IsNClique(List<GraphNode> nodes)
        {
            nodes.Sort((x, y) => x.Label.CompareTo(y.Label));

            for (int i = 0; i < nodes.Count - 1; i++)
            {
                bool result = false;
                List<bool> found = new List<bool>();
                found.AddRange(Enumerable.Repeat(false, nodes.Count - i - 1));
                int j = 0;

                foreach (GraphNode nodeNeighbor in nodes[i].Neighbors.Values)
                {
                    if (!found[j] && nodes[i + j + 1] == nodeNeighbor)
                    {
                        found[j] = true;
                        j++;
                    }

                    if (found.All(foundInner => foundInner))
                    {
                        result = true;
                        break;
                    }
                }

                if (!result)
                    return false;
            }

            return true;
        }

        private List<SortedDictionary<string, GraphNode>> Find3Clique(IEnumerable<GraphNode> graph)
        {
            var lists = new List<SortedDictionary<string, GraphNode>>();
            int cliqueSequnceNumber = 0;
            int count = 0;
            int sum = graph.Count();

            foreach (GraphNode root in graph)
            {
                if (root.ThreeCliqueNumber != 0)
                    continue;
                foreach (var neighbor in root.Neighbors)
                {
                    if (neighbor.Value.ThreeCliqueNumber != 0)
                        continue;
                    SortedList<string, GraphNode> list = FindCommonItems(root.Neighbors, neighbor.Value.Neighbors);
                    foreach (var item in list)
                    {
                        if (item.Value.ThreeCliqueNumber != 0)
                            continue;
                        cliqueSequnceNumber++;

                        var dic = new SortedDictionary<string, GraphNode>();
                        if (root.Label == neighbor.Key || root.Label == item.Key || neighbor.Key == item.Key) continue;

                        cliqueSequnceNumber++;
                        dic.Add(root.Label, root);
                        dic.Add(neighbor.Key, neighbor.Value);
                        dic.Add(item.Key, item.Value);

                        root.ThreeCliqueNumber = cliqueSequnceNumber;
                        neighbor.Value.ThreeCliqueNumber = cliqueSequnceNumber;
                        item.Value.ThreeCliqueNumber = cliqueSequnceNumber;

                        lists.Add(dic);
                    }
                }
                count++;
                //ReportprogressFind3Clique((float)sum / count);
            }
            return lists;
        }

        private SortedDictionary<string, SortedDictionary<string, GraphNode>>
            FindBiggerClique(IGraph graph, IEnumerable<SortedDictionary<string, GraphNode>> clique, int size)
        {
            var list2 = new SortedDictionary<string, SortedDictionary<string, GraphNode>>();
            int count = 0;
            int sum = clique.Count();
            float progrees;
            //  int clusterNumber = 0;
            foreach (var cliqueNodes in clique)
            {
                foreach (GraphNode item in graph.Nodes)
                {
                    //if (item.IsMarkedAsDeleted)
                    //    continue;
                    if (cliqueNodes.ContainsKey(item.Label))
                        continue;
                    if (!Contains(item.Neighbors, cliqueNodes)) continue;

                    AddNodeToBiggerCluster(size, cliqueNodes, item, list2);
                    break;
                }
                count++;
                progrees = (float)count / sum;
                //ReportprogressFind4Clique(progrees);
            }
            return list2;
        }

        private void AddNodeToBiggerCluster(int size, SortedDictionary<string, GraphNode> cliqueNodes, GraphNode item,
                                            SortedDictionary<string, SortedDictionary<string, GraphNode>> list2)
        {
            var dict = new SortedDictionary<string, GraphNode>();
            var stamp = new int[size];
            int index = 0;

            foreach (var item2 in cliqueNodes)
            {
                stamp[index] = item2.Value.SequenceNumber;
                dict.Add(item2.Key, item2.Value);
                index++;
                //item2.Value.IsMarkedAsDeleted = true;
                //item2.Value.ClusterNumber = clusterNumber;
            }

            stamp[index] = item.SequenceNumber;
            dict.Add(item.Label, item);
            //item.IsMarkedAsDeleted = true;
            // item.ClusterNumber = clusterNumber;
            Array.Sort(stamp);
            string key = string.Join(",", stamp);

            if (list2.ContainsKey(key)) //make sure that  duplicate clique not added
            {
                if (FindCommonItems(list2[key], dict).Count > size - 1)
                    return;
            }
            list2.Add(key, dict);
            // clusterNumber++;
        }

        private bool Contains(SortedList<string, GraphNode> list1, SortedDictionary<string, GraphNode> list2)
        {
            if (FindCommonItems(list1, list2).Count > NeighborThreshhold)
                return true;
            return false;
        }

        private Dictionary<string, GraphNode> FindCommonItems(SortedDictionary<string, GraphNode> sortedList1,
                                                              IDictionary<string, GraphNode> sortedList2)
        {
            var nodes = new Dictionary<string, GraphNode>();
            foreach (var item in sortedList1)
            {
                if (sortedList2.ContainsKey(item.Key))
                {
                    nodes.Add(item.Key, item.Value);
                }
            }
            return nodes;
        }

        private Dictionary<string, GraphNode> FindCommonItems(SortedList<string, GraphNode> sortedList1,
                                                              IDictionary<string, GraphNode> sortedList2)
        {
            var nodes = new Dictionary<string, GraphNode>();
            foreach (var item in sortedList1)
            {
                if (sortedList2.ContainsKey(item.Key))
                {
                    nodes.Add(item.Key, item.Value);
                }
            }
            return nodes;
        }

        private SortedList<string, GraphNode> FindCommonItems(SortedList<string, GraphNode> sortedList1,
                                                              SortedList<string, GraphNode> sortedList2)
        {
            var nodes = new SortedList<string, GraphNode>();
            foreach (var item in sortedList1)
            {
                if (sortedList2.ContainsKey(item.Key)) //&& item.Value.ThreeCliqueNumber != 0)
                {
                    nodes.Add(item.Key, item.Value);
                }
            }
            return nodes;
        }

        private SortedList<string, GraphNode> FindCommonItems(SortedList<string, GraphNode> sortedList1,
                                                             SortedList<string, GraphNode> sortedList2,
            int tresholed)
        {
            var nodes = new SortedList<string, GraphNode>();
            int i = 0;
            foreach (var item in sortedList1)
            {
                if (sortedList2.ContainsKey(item.Key) &&
                    !item.Value.IsMarkedAsDeleted)
                {
                    nodes.Add(item.Key, item.Value);
                    i++;
                    if (i >= tresholed)
                        return nodes;
                }
            }
            return nodes;
        }
    }
}
